package baseclass.j_dp.dp.fullBag;

import java.util.Arrays;

/**
 * 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
 * 示例:
 * nums = [1, 2, 3]
 * target = 4
 * 所有可能的组合为：
 * (1, 1, 1, 1)，(1, 1, 2)，(1, 2, 1)，(1, 3)，(2, 1, 1)，(2, 2)， (3, 1)
 * 请注意，顺序不同的序列被视作不同的组合。
 * 因此输出为 7。
 * 进阶：
 * 如果给定的数组中含有负数会怎么样？
 * 问题会产生什么变化？
 * 我们需要在题目中添加什么限制来允许负数的出现？
 *
 * 分析：此题同完全平方数，兑换零钱1类似，暴力遍历所有数组元素
 * @date 2020/3/4 16:59
 */
public class Code03_ChangeMoney3 {
    public static void main(String[] args) {
        int[]arr = {1,2,3};
        System.out.println(dp(arr, 4));
    }

    /**
     *方式1： 暴力回溯
     */
    private static int process1(int[] nums, int target) {

        if (target < 0) return 0;
        //提前剪枝，dp的baseCase,返回的是种数，满足则 + 1
        if (target == 0) return 1;
        int res = 0;
        //当前账户为target的情况下，遍历所有硬币的面值。
        for (int i = 0; i < nums.length; i++) {
            int subProb = process1(nums, target - nums[i]);
            res += subProb;
        }
        return res;
    }

    /**
     *方式2： 记忆性回溯，memo[i]表示当前target为i时的组合数
     */
    private static int process2(int[] nums, int target) {
        //-1表示未知
        int[] memo = new int[target + 1];
        Arrays.fill(memo, -1);
        return doProcess2(nums, target, memo);
    }
    private static int doProcess2(int[] nums, int target, int[] memo) {
        if (target < 0) return 0;
        //提前剪枝
        if (target == 0) return 1;

        if (memo[target] != -1) return memo[target];
        int res = 0;
        //当前账户为target的情况下，遍历所有硬币的面值。
        for (int i = 0; i < nums.length; i++) {
            if (target - nums[i] < 0) continue;
            int subProb = doProcess2(nums, target - nums[i], memo);
            res += subProb;
        }
        return memo[target] = res;
    }

    /**
     * 方式3：DP,dp[i]表示当前目标为 i可被组成的数目
     * 可以理解为当前账户为i下，遍历所有硬币能否兑换。
     * <p>
     * 转移方程:dp[i] = sum(dp[i-num]), 任意 num属于nums
     * <p>
     * dp[0]很特殊
     */
    private static int dp(int[] nums, int target) {
        int[] dp = new int[target + 1];
        //num均为正数。dp[0]很特殊，表示递归基，if(target == 0) return 1
        //如果 i = nums[j] ,dp[i - nums[j]] = 1
        dp[0] = 1;
        //总额从1 开始，一直到target。
        for (int i = 1; i <= target; i++) {
            //当前账户为i的情况下，遍历所有硬币j的面值。
            for (int j = 0; j < nums.length; j++) {
                //总额大于硬币面值
                if (i - nums[j] >= 0)
                    dp[i] = dp[i] + dp[i - nums[j]];
            }
        }
        return dp[target];
    }

}
